# coding=utf-8
#*****************************************************************************
#       Copyright (C) 2008 Arnaud bergeron <abergeron@gmail.com>,
#
#  Distributed under the terms of the GNU General Public License version 2 (GPLv2)
#
#  The full text of the GPLv2 is available at:
#
#                  http://www.gnu.org/licenses/
#*****************************************************************************

include "../ext/stdsage.pxi"
include "../ext/cdefs.pxi"
include "../ext/python.pxi"

from copy import copy
from array import array
from itertools import imap, izip, islice
from sage.rings.infinity import Infinity
from sage.words.utils import id_f
from sage.words.utils cimport clamp, copy_it, haslen, isint, \
                              is_iterable, slice_ok, slice_it
from sage.structure.sage_object cimport SageObject

cpdef MakeContent(obj, max_int=255, mapping=id_f, format=None, part=slice(None)):
    r"""
    Builds the content for a word.
    
    INPUT:
        obj -- a function, an iterator or a list, potentially with a length defined
        mapping -- function, a mapping function for the elements in the iterable.
                   The output must be nonnegative integers.
        max_int -- integer (default 255), the maximum value of the mapping.
        format -- string (default None), the explicit type of obj.  Can be 
                  either 'empty', 'list', 'function', 'iterator' or 'content'.
                  If set to None (the default), the type will be guessed from 
                  the properties of obj.
        part -- slice (default slice(None)), the portion of the object to use
        
    OUTPUT:
        word content -- an object respecting the word content protocol
    
    TESTS:
        sage: from sage.words.word_content import MakeContent
        sage: from itertools import count, imap, repeat
        sage: len(MakeContent(None))
        0
        sage: len(MakeContent(None, format='empty'))
        0
        sage: c = MakeContent(['a', 'b'], format='empty')
        Traceback (most recent call last):
        ...
        TypeError: obj is not None
        sage: len(MakeContent(['0', '1', '1'], 1, int))
        3
        sage: len(MakeContent(['0', '1', '1'], 1, int, format='list'))
        3
        sage: MakeContent(10, format='list')
        Traceback (most recent call last):
        ...
        TypeError: obj does not support list operations
        sage: c = MakeContent(lambda x: x%2, 1)
        sage: len(MakeContent(lambda x: x%3, 2, part=slice(0,10)))
        10
        sage: c = MakeContent(repeat(1), 1)
        sage: len(MakeContent(count(), 9, part=slice(10)))
        10
        sage: len(MakeContent(count(), 9, part=slice(10, 0, -2)))
        5
    """
    # 0 is a special value, don't let users set it, even accidently
    if max_int == 0:
        max_int = 1
    
    if format is None:
        if is_Content(obj):
            format = 'content'
        elif obj is None:
            format = 'empty'
        elif is_iterable(obj):
            if haslen(obj):
                format = 'list'
            else:
                format = 'iterator'
        elif callable(obj):
            format = 'function'
        else:
            pass # Don't set format if we don't know

    if format == 'empty':
        if obj is not None:
            raise TypeError, "obj is not None"
        return ListContent((), max_int, mapping)[part]
    elif format == 'list':
        if not (is_iterable(obj) and haslen(obj)):
            raise TypeError, "obj does not support list operations"
        return ListContent(obj, max_int, mapping)[part]
    elif format == 'function':
        if not callable(obj):
            raise TypeError, "obj is not callable"
        return FunctionContent(obj, mapping)[part]
    elif format == 'iterator':
        if not is_iterable(obj):
            raise TypeError, "obj is not iterable"
        return IteratorContent(obj, max_int, mapping)[part]
    elif format == 'content':
        if not is_Content(obj):
            raise TypeError, "obj is not a WordContent"
        return obj[part]
    raise NotImplementedError
    
cpdef is_Content(obj):
    r"""
    Returns True if obj is the content of a word.
    
    EXAMPLES:
        sage: from sage.words.word_content import MakeContent, is_Content
        sage: is_Content(33)
        False
        sage: is_Content(MakeContent([0, 1, 0], 1, sage.words.utils.id_f))
        True
    """
    return PY_TYPE_CHECK(obj, WordContent)

cdef inline bint _rich_to_bool(int op, int r):
    if op == Py_LT:  #<
        return (r  < 0)
    elif op == Py_EQ: #==
        return (r == 0)
    elif op == Py_GT: #>
        return (r  > 0)
    elif op == Py_LE: #<=
        return (r <= 0)
    elif op == Py_NE: #!=
        return (r != 0)
    elif op == Py_GE: #>=
        return (r >= 0)

cdef class WordContent:
    def __richcmp__(left, right, int op):
        r"""
        Compares two contents according to the data they contain.  
        
        The types of the contents doesn't matter.
        
        TESTS:
            sage: c1 = sage.words.word_content.ListContent([1, 2, 1, 1], 3)
            sage: c2 = sage.words.word_content.ListContent([1, 2, 3], 3)
            sage: c3 = sage.words.word_content.ListContent([1, 4], 4)
            sage: c1 < c2
            True
            sage: c2 < c2
            False
            sage: c3 < c2
            False
            sage: c1 <= c2
            True
            sage: c2 <= c2
            True
            sage: c3 <= c2
            False
            sage: c1 == c2
            False
            sage: c2 == c2
            True
            sage: c3 == c2
            False
            sage: c1 > c2
            False
            sage: c2 > c2
            False
            sage: c3 > c2
            True
            sage: c1 >= c2
            False
            sage: c2 >= c2
            True
            sage: c3 >= c2
            True
            sage: c1 != c2
            True
            sage: c2 != c2
            False
            sage: c3 != c2
            True
            sage: c2 == None
            False
            sage: c1 != [1, 2, 1, 1]
            True
        """
        cdef unsigned long i, j
        if not is_Content(right):
            return NotImplemented
        if haslen(left) and haslen(right):
            for (i, j) in izip(left, right):
                if i != j:
                    return _rich_to_bool(op, i - j)
            return _rich_to_bool(op, len(left) - len(right))
        return NotImplemented
    
    def concatenate(self, WordContent other not None):
        r"""
        Method to concatenate two contents together.
        
        TESTS:
            sage: from sage.words.word_content import MakeContent
            sage: list(MakeContent([1], 1).concatenate(MakeContent([2, 3, 4], 4)))
            [1, 2, 3, 4]
        """
        if not (haslen(self) and haslen(other)):
            raise ValueError, "cannot concatenate infinite words"
        return ConcatenateContent(self._get_list() + other._get_list())
    
    cdef tuple _get_list(self):
        r"""
        Returns self as a list of contents suitable for concatenate
        """
        return (self,)
    
    cpdef _check_getitem_args(self, key):
        r"""
        Does all the type and range checking for the key argument to 
        __getitem__().  Also takes care of normalizing the ranges specified
        by slicing to values suitable for xrange() or similar in the finite
        case.  In the infinite case a stop value of None, will stay as None
        since no end can be defined.
        
        TESTS:
            # Generic Cases
            sage: w = sage.words.word_content.WordContent()
            sage: w._check_getitem_args(1)
            1
            sage: w._check_getitem_args("abc")
            Traceback (most recent call last):
            ...
            TypeError: word indices must be integers
            sage: w._check_getitem_args(slice(1, 2, 3))
            slice(1, 2, 3)
            sage: w._check_getitem_args(slice("a"))
            Traceback (most recent call last):
            ...
            TypeError: word indices must be integers
            sage: w._check_getitem_args(slice("a", 1))
            Traceback (most recent call last):
            ...
            TypeError: word indices must be integers
            sage: w._check_getitem_args(slice(1, 1, "a"))
            Traceback (most recent call last):
            ...
            TypeError: word indices must be integers
            
            # Finite Cases
            sage: f = sage.words.word_content.ListContent(range(10), 9)
            sage: f._check_getitem_args(slice(None, None, None))
            slice(0, 10, 1)
            sage: f._check_getitem_args(slice(None, 0, None))
            slice(0, 0, 1)
            sage: f._check_getitem_args(slice(None, 1, None))
            slice(0, 1, 1)
            sage: f._check_getitem_args(slice(None, -1, None))
            slice(0, 9, 1)
            sage: f._check_getitem_args(slice(None, 11, None))
            slice(0, 10, 1)
            sage: f._check_getitem_args(slice(None, 10, None))
            slice(0, 10, 1)
            sage: f._check_getitem_args(slice(None, 9, None))
            slice(0, 9, 1)
            sage: f._check_getitem_args(slice(None, -9, None))
            slice(0, 1, 1)
            sage: f._check_getitem_args(slice(None, -10, None))
            slice(0, 0, 1)
            sage: f._check_getitem_args(slice(None, -11, None))
            slice(0, 0, 1)
            sage: f._check_getitem_args(slice(0, None, None))
            slice(0, 10, 1)
            sage: f._check_getitem_args(slice(1, None, None))
            slice(1, 10, 1)
            sage: f._check_getitem_args(slice(-1, None, None))
            slice(9, 10, 1)
            sage: f._check_getitem_args(slice(11, None, None))
            slice(10, 10, 1)
            sage: f._check_getitem_args(slice(10, None, None))
            slice(10, 10, 1)
            sage: f._check_getitem_args(slice(9, None, None))
            slice(9, 10, 1)
            sage: f._check_getitem_args(slice(-9, None, None))
            slice(1, 10, 1)
            sage: f._check_getitem_args(slice(-10, None, None))
            slice(0, 10, 1)
            sage: f._check_getitem_args(slice(-11, None, None))
            slice(0, 10, 1)
            sage: f._check_getitem_args(slice(None, None, -1))
            slice(9, -1, -1)
            sage: f._check_getitem_args(slice(None, 0, -1))
            slice(9, 0, -1)
            sage: f._check_getitem_args(slice(None, 1, -1))
            slice(9, 1, -1)
            sage: f._check_getitem_args(slice(None, -1, -1))
            slice(9, 9, -1)
            sage: f._check_getitem_args(slice(None, 11, -1))
            slice(9, 9, -1)
            sage: f._check_getitem_args(slice(None, 10, -1))
            slice(9, 9, -1)
            sage: f._check_getitem_args(slice(None, 9, -1))
            slice(9, 9, -1)
            sage: f._check_getitem_args(slice(None, -10, -1))
            slice(9, 0, -1)
            sage: f._check_getitem_args(slice(None, -11, -1))
            slice(9, -1, -1)
            sage: f._check_getitem_args(slice(None, -12, -1))
            slice(9, -1, -1)
            sage: f._check_getitem_args(slice(0, None, -1))
            slice(0, -1, -1)
            sage: f._check_getitem_args(slice(1, None, -1))
            slice(1, -1, -1)
            sage: f._check_getitem_args(slice(-1, None, -1))
            slice(9, -1, -1)
            sage: f._check_getitem_args(slice(10, None, -1))
            slice(9, -1, -1)
            sage: f._check_getitem_args(slice(9, None, -1))
            slice(9, -1, -1)
            sage: f._check_getitem_args(slice(8, None, -1))
            slice(8, -1, -1)
            sage: f._check_getitem_args(slice(-10, None, -1))
            slice(0, -1, -1)
            sage: f._check_getitem_args(slice(-11, None, -1))
            slice(-1, -1, -1)
            sage: f._check_getitem_args(slice(-12, None, -1))
            slice(-1, -1, -1)
            sage: f._check_getitem_args(slice(None, None, 0))
            Traceback (most recent call last):
            ...
            ValueError: slice step cannot be zero
            sage: f._check_getitem_args(9)
            9
            sage: f._check_getitem_args(10)
            Traceback (most recent call last):
            ...
            IndexError: word index out of range
            sage: f._check_getitem_args(0)
            0
            sage: f._check_getitem_args(-1)
            9
            sage: f._check_getitem_args(-10)
            0
            sage: f._check_getitem_args(-11)
            Traceback (most recent call last):
            ...
            IndexError: word index out of range
            
            # Infinite Cases
            sage: from itertools import count
            sage: i = sage.words.word_content.IteratorContent(count(), 664266)
            sage: i._check_getitem_args(slice(None, None, None))
            slice(0, None, 1)
            sage: i._check_getitem_args(slice(None, 0, None))
            slice(0, 0, 1)
            sage: i._check_getitem_args(slice(None, 1, None))
            slice(0, 1, 1)
            sage: i._check_getitem_args(slice(None, -1, None))
            Traceback (most recent call last):
            ...
            IndexError: negative index on infinite word
            sage: i._check_getitem_args(slice(0, None, None))
            slice(0, None, 1)
            sage: i._check_getitem_args(slice(1, None, None))
            slice(1, None, 1)
            sage: i._check_getitem_args(slice(-1, None, None))
            Traceback (most recent call last):
            ...
            IndexError: negative index on infinite word
            sage: i._check_getitem_args(slice(None, None, -1))
            Traceback (most recent call last):
            ...
            ValueError: negative step and no defined start
            sage: i._check_getitem_args(slice(None, 0, -1))
            Traceback (most recent call last):
            ...
            ValueError: negative step and no defined start
            sage: i._check_getitem_args(slice(None, -1, -1))
            Traceback (most recent call last):
            ...
            ValueError: negative step and no defined start
            sage: i._check_getitem_args(slice(0, None, -1))
            slice(0, -1, -1)
            sage: i._check_getitem_args(slice(-1, None, -1))
            Traceback (most recent call last):
            ...
            IndexError: negative index on infinite word
            sage: i._check_getitem_args(slice(None, None, 0))
            Traceback (most recent call last):
            ...
            ValueError: slice step cannot be zero
            sage: i._check_getitem_args(1)
            1
            sage: i._check_getitem_args(-1)
            Traceback (most recent call last):
            ...
            IndexError: negative index on infinite word
        """
        if slice_ok(key):
            start, stop, step = key.start, key.stop, key.step
            if step is None:
                step = 1
            if step == 0:
                raise ValueError, "slice step cannot be zero"
            if haslen(self):
                if start is None:
                    if step < 0:
                        start = len(self) - 1
                    else:
                        start = 0
                else:
                    if start < 0:
                        start += len(self)
                    if step < 0:
                        start = clamp(start, -1, len(self) - 1)
                    else:
                        start = clamp(start, 0, len(self))
                if stop is None:
                    if step < 0:
                        stop = -1
                    else:
                        stop = len(self)
                else:
                    if stop < 0:
                        stop += len(self)
                    if step < 0:
                        stop = clamp(stop, -1, len(self) - 1)
                    else:
                        stop = clamp(stop, 0, len(self))
            else:
                if start is None:
                    if step < 0:
                        raise ValueError, "negative step and no defined start"
                    else:
                        start = 0
                else:
                    start = self._check_getitem_args(start)
                if stop is None:
                    if step < 0:
                       stop = -1
                else:
                    stop = self._check_getitem_args(stop)
            return slice(start, stop, step)
        elif isint(key):
            key = int(key)
            if haslen(self):
                if key < 0:
                    key += len(self)
                if key < 0 or key >= len(self):
                    raise IndexError, "word index out of range"
            else:
                if key < 0:
                    raise IndexError, "negative index on infinite word"
            return key
        else:
            raise TypeError, "word indices must be integers"

cdef class ListContent(WordContent):
    cdef _list
    
    def __init__(self, l, unsigned long maxint, trans=id_f):
        r"""
        INPUT:
            l -- list
            trans -- function (default identity), defines a mapping between the objects in l and the nonnegative integers
            
        TESTS:
            sage: c = sage.words.word_content.ListContent([0, 1, 1, 2, 1], 2)
            sage: c == loads(dumps(c))
            True
        """
        if maxint == 0:
            self._list = l
        else:
            if maxint < 256:
                typecode = 'B'
            elif maxint < 65536:
                typecode = 'I'
            elif maxint < 4294967296:
                typecode = 'L'
            else:
                raise ValueError, "maxint (=%r) too large"% maxint
            self._list = array('B', imap(trans, l))
    
    def __getstate__(self):
        r"""
        Support for pickle and copy.
        
        TESTS:
            sage: from sage.words.word_content import ListContent
            sage: ListContent('12345', 5, int).__getstate__()
            array('B', [1, 2, 3, 4, 5])
        """
        return self._list
    
    def __setstate__(self, l):
        r"""
        Support for pickle and copy.
        
        TESTS:
            sage: from sage.words.word_content import ListContent
            sage: from array import array
            sage: l = ListContent([], 1)
            sage: l.__setstate__(array('B', [1, 2, 3]))
            sage: list(l)
            [1, 2, 3]
        """
        self._list = l
    
    def __iter__(self):
        r"""
        TESTS:
            sage: list(sage.words.word_content.ListContent('012345', 5, int)) # indirect test
            [0, 1, 2, 3, 4, 5]
        """
        return iter(self._list)
    
    def __len__(self):
        r"""
        TESTS:
            sage: len(sage.words.word_content.ListContent([0, 1, 0, 0, 1], 1))
            5
        """
        return len(self._list)
    
    def __getitem__(self, key):
        r"""
        TESTS:
            sage: from sage.words.word_content import ListContent
            sage: w = ListContent('012345', 5, int)
            sage: e = ListContent('', 1, int)
            sage: w__2 = ListContent('45', 5, int)
            sage: w_2 = ListContent('01', 1, int)
            sage: w__1 = ListContent('01234', 4, int)
            sage: w_s2 = ListContent('024', 4, int)
            sage: w_s_2 = ListContent('531', 5, int)
            sage: w[:] == w
            True
            sage: w[0:] == w
            True
            sage: w[10:] == e
            True
            sage: w[-2:] == w__2
            True
            sage: w[-10:] == w
            True
            sage: w[:0] == e
            True
            sage: w[:2] == w_2
            True
            sage: w[:10] == w
            True
            sage: w[:-1] == w__1
            True
            sage: w[:-10] == e
            True
            sage: w[::2] == w_s2
            True
            sage: w[::-2] == w_s_2
            True
            sage: w[::0]
            Traceback (most recent call last):
            ...
            ValueError: slice step cannot be zero
            sage: w[0]
            0
            sage: w[5]
            5
            sage: w[6]
            Traceback (most recent call last):
            ...
            IndexError: word index out of range
            sage: w[-1]
            5
            sage: w[-6]
            0
            sage: w[-7]
            Traceback (most recent call last):
            ...
            IndexError: word index out of range
        """
        key = self._check_getitem_args(key)
        if isinstance(key, slice):
            if key.stop == -1:
                key = slice(key.start, None, key.step)
            return ListContent(self._list[key], 0)
        else:
            return self._list[key]

cdef class FunctionContent_slice:
    cdef _func
    cdef _start, _step
    
    def __init__(self, func, start, step):
        r"""
        Create a slice of a function.
        
        NOTE:
            No error checking is done on the arguments.
        
        INPUT:
            func -- a function defined over the positive integers
            start -- the start index
            step -- the stepping size
        
        OUTPUT:
            function -- the original function with its input mapped to start + x*step
        
        TESTS:
            sage: from sage.words.word_content import FunctionContent_slice
            sage: from sage.words.utils import id_f
            sage: f = FunctionContent_slice(id_f, 10, 2)
            sage: f(0)
            10
            sage: f(1)
            12
            sage: f2 = copy(f)
            sage: f2 is f
            False
            sage: f2(2)
            14
            sage: FunctionContent_slice(id_f, 3, -3)(1)
            0
        """
        if isinstance(func, FunctionContent_slice):
            raise TypeError
        self._func = func
        self._start = start
        self._step = step
    
    def __call__(self, i):
        r"""
        Returns the value of the wrapped function applied to start + i*step.
        
        TESTS:
            sage: from sage.words.word_content import FunctionContent_slice
            sage: from sage.words.utils import id_f
            sage: FunctionContent_slice(id_f, 0, 1)(0)
            0
        """
        return self._call(i)
    
    cdef _call(self, i):
        return self._func(self._start + self._step*i)
    
    cdef addstart(self, val):
        self._start = self._start + val*self._step
    
    cdef mulstep(self, val):
        self._step = self._step * val
    
    def __getstate__(self):
        r"""
        Saves the state for pickle.
        
        TESTS:
            sage: from sage.words.word_content import FunctionContent_slice
            sage: from sage.words.utils import id_f
            sage: FunctionContent_slice(id_f, 3, -3).__getstate__()
            (<built-in function id_f>, 3, -3)
        """
        return (self._func, self._start, self._step)
    
    def __setstate__(self, state):
        r"""
        Restores state for pickle.
        
        TESTS:
            sage: from sage.words.word_content import FunctionContent_slice
            sage: from sage.words.utils import id_f
            sage: f = copy(FunctionContent_slice(id_f, 5, -2)) # indirect test
            sage: f(0)
            5
            sage: f(1)
            3
            sage: f(2)
            1
        """
        self._func = state[0]
        self._start = state[1]
        self._step = state[2]

cdef class FunctionContent_iter(SageObject):
    cdef public _copy_ok_
    cdef FunctionContent_slice _func
    cdef _len, _i
    def __init__(self, func, l):
        r"""
        Specialized iterator class for FunctionContents
        
        TESTS:
            sage: from sage.words.word_content import FunctionContent_iter, FunctionContent_slice
            sage: from sage.words.utils import id_f
            sage: it = FunctionContent_iter(FunctionContent_slice(id_f, 0, 1), 10)
        """
        self._func = func
        self._len = l
        self._i = 0
    
    def __next__(self):
        r"""
        Gives the next element in the sequence
        
        TESTS:
            sage: from sage.words.word_content import FunctionContent_iter, FunctionContent_slice
            sage: from sage.words.utils import id_f
            sage: list(FunctionContent_iter(FunctionContent_slice(id_f, 0, 1), 10)) # indirect test
            [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
        """
        if self._i < self._len:
            self._i += 1
            return self._func._call(self._i - 1)
        else:
            raise StopIteration
    
    def __iter__(self):
        r"""
        Returns self
        
        TESTS:
            sage: it = sage.words.word_content.FunctionContent_iter(sage.words.word_content.FunctionContent_slice(sage.words.utils.id_f, 0, 1), 0)
            sage: iter(it) is it
            True
        """
        return self
    
    def __getstate__(self):
        r"""
        Saves the state for pickle.
        
        TESTS:
            sage: from sage.words.word_content import FunctionContent_iter, FunctionContent_slice
            sage: from sage.words.utils import id_f
            sage: FunctionContent_iter(FunctionContent_slice(id_f, 0, 1), 10).__getstate__()
            (<sage.words.word_content.FunctionContent_slice object at 0x...>, 10, 0)
        """
        return (self._func, self._len, self._i)
    
    def __setstate__(self, state):
        r"""
        Restores state for pickle.
        
        TESTS:
            sage: from sage.words.word_content import FunctionContent_iter, FunctionContent_slice
            sage: from sage.words.utils import id_f
            sage: it = FunctionContent_iter(FunctionContent_slice(id_f, 0, 1), 10)
            sage: it.next()
            0
            sage: copy(it).next()
            1
            sage: it.next()
            1
        """
        self._func = state[0]
        self._len = state[1]
        self._i = state[2]

cdef class FunctionContent(WordContent):
    cdef readonly FunctionContent_slice _func
    cdef _len, _trans
    
    def __init__(self, func, trans=id_f):
        r"""
        INPUT:
            func -- callable
            trans -- callable (default: identity), defines a mapping between the objects returned by func and the nonnegative integers.
        
        NOTE:
            Unnamed functions do not pickle.
        
        TESTS:
            sage: c = sage.words.word_content.FunctionContent(sage.words.utils.id_f)[:10]
            sage: c == loads(dumps(c))
            True
        """
        if not PY_TYPE_CHECK(func, FunctionContent_slice):
            func = FunctionContent_slice(func, 0, 1)
        self._func = func
        self._trans = trans
        self._len = Infinity

    def __getstate__(self):
        r"""
        Saves the state for pickle.
        
        TESTS:
            sage: from sage.words.word_content import FunctionContent
            sage: FunctionContent(sage.words.utils.id_f).__getstate__()
            (<sage.words.word_content.FunctionContent_slice object at 0x...>, <built-in function id_f>, +Infinity)
        """
        return (self._func, self._trans, self._len)
    
    def __setstate__(self, state):
        r"""
        Restores state for pickle.
        
        TESTS:
            sage: from sage.words.word_content import FunctionContent, FunctionContent_slice
            sage: f = FunctionContent(sage.words.utils.id_f)
            sage: f.__setstate__((FunctionContent_slice(sage.words.utils.id_f, 0, 1), sage.words.utils.id_f, 10))
            sage: len(f)
            10
        """
        self._func = state[0]
        self._trans = state[1]
        self._len = state[2]
    
    def __iter__(self):
        r"""
        TESTS:
            sage: list(sage.words.word_content.FunctionContent(sage.words.utils.id_f)[:6]) # indirect test
            [0, 1, 2, 3, 4, 5]
        """
        return FunctionContent_iter(self._func, self._len)
    
    def __len__(self):
        r"""
        TESTS:
            sage: c = sage.words.word_content.FunctionContent(sage.words.utils.id_f)
            sage: len(c)
            Traceback (most recent call last):
            ...
            TypeError: 'PlusInfinity' object cannot be interpreted as an index
            sage: c = c[:10]
            sage: len(c)
            10
        """
        return self._len
    
    def __getitem__(self, key):
        r"""
        TESTS:
            sage: from sage.words.utils import id_f
            sage: from sage.words.word_content import FunctionContent, ListContent
            sage: w = FunctionContent(id_f);
            sage: e = ListContent('', 5, int)
            sage: w__2 = ListContent('45', 5, int)
            sage: w_2 = ListContent('01', 5, int)
            sage: w__1 = ListContent('01234', 5, int)
            sage: w_s2 = ListContent('024', 5, int)
            sage: w_s_2 = ListContent('531', 5, int)
            sage: w[:]          # random results
            <sage.words.word_content.FunctionContent object at 0xe499c30>
            sage: w[0:]         # random results
            <sage.words.word_content.FunctionContent object at 0xe499c50>
            sage: w[1:]         # random results
            <sage.words.word_content.FunctionContent object at 0xe499c30>
            sage: w[:0] == e
            True
            sage: w[:5] == w__1
            True
            sage: w[::2]        # random results
            <sage.words.word_content.FunctionContent object at 0xe499bf0>
            sage: w[::0]
            Traceback (most recent call last):
            ...
            ValueError: slice step cannot be zero
            sage: w[5]
            5
            sage: w[-1]
            Traceback (most recent call last):
            ...
            IndexError: negative index on infinite word
            sage: w = w[:6]
            sage: w[:] == w
            True
            sage: w[0:] == w
            True
            sage: w[10:] == e
            True
            sage: w[-2:] == w__2
            True
            sage: w[-10:] == w
            True
            sage: w[:0] == e
            True
            sage: w[:2] == w_2
            True
            sage: w[:10] == w
            True
            sage: w[:-1] == w__1
            True
            sage: w[:-10] == e
            True
            sage: w[::2] == w_s2
            True
            sage: w[::-2] == w_s_2
            True
            sage: w[::0]
            Traceback (most recent call last):
            ...
            ValueError: slice step cannot be zero
            sage: w[0]
            0
            sage: w[5]
            5
            sage: w[6]
            Traceback (most recent call last):
            ...
            IndexError: word index out of range
            sage: w[-1]
            5
            sage: w[-6]
            0
            sage: w[-7]
            Traceback (most recent call last):
            ...
            IndexError: word index out of range
        """
        cdef FunctionContent res
        cdef FunctionContent_slice fn
        key = self._check_getitem_args(key)
        if isinstance(key, slice):
            fn = copy(self._func)
            fn.addstart(key.start)
            fn.mulstep(key.step)
            res = FunctionContent(fn, self._trans)
            if key.stop is not None:
                res._len = int((key.stop - key.start)/key.step)
            return res
        else:
            return self._trans(self._func._call(key))

cdef class IteratorContent(WordContent):
    cdef _iter, _len, _trans
    cdef unsigned long _max
    
    def __init__(self, it, unsigned long maxint, trans=id_f):
        r"""
        INPUT:
            it -- iterator
            trans -- function (default identity), defines a mapping between the objects returned by it and the nonnegative integers.
        
        NOTE:
            It appears that islice does not pickle correctly causing
            various errors when reloading.  Also, most iterators
            do not support copying and should not support pickling by 
            extension.
        
        TESTS:
            sage: from itertools import count
            sage: c = sage.words.word_content.IteratorContent(count(), 9)[:10]

            #sage: c == loads(dumps(c)) # broken because of islice
            #True
        """
        self._iter = iter(it)
        self._len = Infinity
        self._trans = trans
        self._max = maxint
    
    def __getstate__(self):
        r"""
        Saves the state for pickle.
        
        TESTS:
            sage: from sage.words.word_content import IteratorContent
            sage: from itertools import count
            sage: IteratorContent(count(), 4000000000).__getstate__()
            (count(0), +Infinity, <built-in function id_f>, 4000000000L)
        """
        return (self._iter, self._len, self._trans, self._max)
    
    def __setstate__(self, state):
        r"""
        Restores state for pickle.
        
        TESTS:
            sage: from sage.words.word_content import IteratorContent
            sage: from itertools import count
            sage: c = IteratorContent(count(), 4000000000)
            sage: c.__setstate__((count(2), 10, sage.words.utils.id_f, 11))
            sage: len(c)
            10
        """
        self._iter = state[0]
        self._len = state[1]
        self._trans = state[2]
        self._max = state[3]
    
    def __iter__(self):
        r"""
        TESTS:
            sage: from itertools import count
            sage: list(sage.words.word_content.IteratorContent(count(), 5)[:6]) # indirect test
            [0, 1, 2, 3, 4, 5]
        """
        return imap(self._trans, self._get_it())
    
    cdef _get_it(self):
        self._iter, new = copy_it(self._iter)
        return new
    
    def __len__(self):
        r"""
        TESTS:
            sage: from itertools import count
            sage: c = sage.words.word_content.IteratorContent(count(), 9)
            sage: len(c)
            Traceback (most recent call last):
            ...
            TypeError: 'PlusInfinity' object cannot be interpreted as an index
            sage: c = c[:10]
            sage: len(c)
            10
        """
        return self._len
    
    def __getitem__(self, key):
        r"""
        TESTS:
            sage: from itertools import count
            sage: from sage.words.word_content import IteratorContent, ListContent
            sage: w = IteratorContent(count(), 5)
            sage: e = ListContent('', 5, int)
            sage: w__2 = ListContent('45', 5, int)
            sage: w_2 = ListContent('01', 5, int)
            sage: w__1 = ListContent('01234', 5, int)
            sage: w_s2 = ListContent('024', 5, int)
            sage: w_s_2 = ListContent('531', 5, int)
            sage: w[:]          # random results
            <sage.words.word_content.IteratorContent object at 0xe499c30>
            sage: w[0:]         # random results
            <sage.words.word_content.IteratorContent object at 0xe499c50>
            sage: w[1:]         # random results
            <sage.words.word_content.IteratorContent object at 0xe499c30>
            sage: w[:0] == e
            True
            sage: w[:5] == w__1
            True
            sage: w[::2]        # random results
            <sage.words.word_content.IteratorContent object at 0xe499bf0>
            sage: w[::0]
            Traceback (most recent call last):
            ...
            ValueError: slice step cannot be zero
            sage: w[5]
            5
            sage: w[-1]
            Traceback (most recent call last):
            ...
            IndexError: negative index on infinite word
            sage: w = w[:6]
            sage: w[:] == w
            True
            sage: w[0:] == w
            True
            sage: w[10:] == e
            True
            sage: w[-2:] == w__2
            True
            sage: w[-10:] == w
            True
            sage: w[:0] == e
            True
            sage: w[:2] == w_2
            True
            sage: w[:10] == w
            True
            sage: w[:-1] == w__1
            True
            sage: w[:-10] == e
            True
            sage: w[::2] == w_s2
            True
            sage: w[::-2] == w_s_2
            True
            sage: w[::0]
            Traceback (most recent call last):
            ...
            ValueError: slice step cannot be zero
            sage: w[0]
            0
            sage: w[5]
            5
            sage: w[6]
            Traceback (most recent call last):
            ...
            IndexError: word index out of range
            sage: w[-1]
            5
            sage: w[-6]
            0
            sage: w[-7]
            Traceback (most recent call last):
            ...
            IndexError: word index out of range
        """
        cdef IteratorContent res
        key = self._check_getitem_args(key)
        if isinstance(key, slice):
            if key.step < 0:
                if key.stop == -1:
                    key = slice(key.start, None, key.step)
                if haslen(self):
                    return ListContent(slice_it(self, len(self), key), self._max)
                else:
                    return ListContent(slice_it(self, \
                                int(key.start - key.stop), key), self._max)
            else:
                res = IteratorContent(islice(self._get_it(), key.start, \
                                             key.stop, key.step), self._max, \
                                             self._trans)
                if key.stop is not None:
                    res._len = int((key.stop - key.start)/key.step)
                return res
        else:
            return islice(self, key, None).next()

cdef class ConcatenateContent_iter(SageObject):
    cdef _its, _itc
    def __init__(self, l):
        r"""
        TESTS:
            sage: from sage.words.word_content import ConcatenateContent_iter
            sage: it = ConcatenateContent_iter([['a', 'b'], ['c', 'd', 'e']])

            #sage: list(loads(dumps(it))) # broken: can't pickle listiterators
            #['a', 'b', 'c', 'd', 'e']
        """
        self._itc = iter(l)
        try:
            self._its = iter(self._itc.next())
        except StopIteration:
            self._its = None
    
    def __getstate__(self):
        r"""
        Saves the state for pickle.
        
        TESTS:
            sage: from sage.words.word_content import ConcatenateContent_iter
            sage: ConcatenateContent_iter([['a', 'b'], ['c', 'c'], ['d']]).__getstate__()
            (<listiterator object at 0x...>, <listiterator object at 0x...>)
        """
        return (self._its, self._itc)
    
    def __setstate__(self, state):
        r"""
        Restores state for pickle.
        
        TESTS:
            sage: from sage.words.word_content import ConcatenateContent_iter
            sage: c = ConcatenateContent_iter([[3, 4], [5]])
            sage: c.__setstate__(c.__getstate__())
            sage: list(c)
            [3, 4, 5]
        """
        self._its = state[0]
        self._itc = state[1]
    
    def __iter__(self):
        r"""
        TESTS:
            sage: from sage.words.word_content import ConcatenateContent_iter
            sage: c = ConcatenateContent_iter([[3, 4], [5]])
            sage: iter(c) is c
            True
        """
        return self
    
    def __next__(self):
        r"""
        TESTS:
            sage: from sage.words.word_content import ConcatenateContent_iter
            sage: c = ConcatenateContent_iter([[1, 1, 2], [3, 4], [5]])
            sage: list(c) # indirect test
            [1, 1, 2, 3, 4, 5]
            sage: list(c)
            []
        """
        if self._its is None:
            raise StopIteration
        try:
            return self._its.next()
        except StopIteration:
            try:
                self._its = iter(self._itc.next())
            except StopIteration:
                self._its = None
                raise StopIteration
        return self.next()

cdef class ConcatenateContent(FunctionContent):
    r"""
    Class that acts as a function to concatenate contents.
    """
    
    cdef _list
    
    def __init__(self, l):
        r"""
        TESTS:
            sage: from sage.words.word_content import ConcatenateContent, MakeContent
            sage: c = ConcatenateContent((MakeContent([1, 2], 2),))
            sage: len(c)
            2
            sage: c = ConcatenateContent((MakeContent('1221', 2, int), MakeContent('2112', 2, int)))
            sage: len(c)
            8
            sage: c == loads(dumps(c))
            True
        """
        self._list = l
        super(ConcatenateContent, self).__init__(self)
        self._len = sum(imap(len, self._list))
    
    def __getstate__(self):
        r"""
        Saves the state for pickle.
        
        TESTS:
            sage: from sage.words.word_content import ConcatenateContent, MakeContent
            sage: ConcatenateContent((MakeContent('1221', 2, int), MakeContent('2112', 2, int))).__getstate__()
            ((<sage.words.word_content.ListContent object at 0x...>, <sage.words.word_content.ListContent object at 0x...>), 8)
        """
        return self._list, self._len
    
    def __setstate__(self, state):
        r"""
        Restores state for pickle.
        
        TESTS:
            sage: from sage.words.word_content import ConcatenateContent
            sage: c = ConcatenateContent([[3, 4], [5]])
            sage: c.__setstate__(c.__getstate__())
            sage: list(c)
            [3, 4, 5]
        """
        self._list = state[0]
        self._len = state[1]
    
    def __iter__(self):
        r"""
        TESTS:
            sage: from sage.words.word_content import ConcatenateContent, MakeContent
            sage: list(ConcatenateContent((MakeContent('012', 2, int), MakeContent([3, 4, 5], 5)))) # indirect test
            [0, 1, 2, 3, 4, 5]
        """
        return ConcatenateContent_iter(self._list)
    
    cdef tuple _get_list(self):
        r"""
        Optimization: for ConcatenateContents return the internal list.
        """
        return self._list
    
    def __call__(self, key):
        r"""
        Returns the character at position key in the word.
        
        EXAMPLES:
            sage: from sage.words.word_content import ConcatenateContent, MakeContent
            sage: c = ConcatenateContent((MakeContent('1221', 2, int), MakeContent('2112', 2, int)))
            sage: c(0)
            1
            sage: c(7)
            2
        """
        for c in self._list:
            if (key - len(c) < 0):
                return c[key]
            key -= len(c)
